package Josephus

/*
时间复杂度：O(logN)
空间复杂度：O(1)

假设fx[i]表示[1,i]区间从左到右间隔删除左边剩余的数编号
fy[i]表示[1,i]区间从右到左间隔删除最后右边剩余的数编号
两者对称，得公式一:
fx[i]+fy[i] = i+1

fx[i]=2*fy[i/2]

=> fx[i]=2(i/2+1-fy[i/2])

详细参考:https://leetcode-cn.com/problems/elimination-game/solution/gong-shui-san-xie-yue-se-fu-huan-yun-yon-x60m/

*/

func lastRemaining1(n int) int {
	if n == 1 {
		return 1
	}
	return 2 * (n/2 + 1 - lastRemaining1(n/2))
}
